package com.daji.search_and_sort;

import java.util.Arrays;
import java.util.List;

public class InsertionSort {

    public static void main(String[] args) {
        int[] arr = {7, 6, 12, -11, 5, 12, 0, 3, 7, 20};
        insertionSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    //直接插入排序
    private static void insertionSort(int[] arr) {
        int arrLen = arr.length;
        for (int i = 1; i < arrLen; i++) { //选择元素来插入
            int temp = arr[i]; //要插入的元素

            if (temp >= arr[i - 1]) { //如果要插入的元素大于等于已排好序的数组的最大位，就插入到已排序数组的末尾
                continue;
            }

            int j = i; //临时变量j
            //这里利用性质：&& 和 || 是短路运算！
            //&&的左侧如果是假，就不运行&&的右侧了 (因为整个表达式已经是false了。当然，如果&&左边是真，仍然需要运行一下右侧)
            //||的左侧如果是真，就不运行||的右侧了（因为整个表达式已经是true了。当然，如果||左边是假，仍然需要运行一下右侧）
            //短路运算查看下面的专栏，一看便知： https://zhuanlan.zhihu.com/p/25285955
            while (j > 0 && temp < arr[j - 1]) {
                arr[j] = arr[j - 1]; //当前元素后移，为新插入元素腾出空间
                j--;
            }
            arr[j] = temp; //插入到那个腾出的空间中
        }
    }
}
